package com.hanxiaozhang.stackandqueue;

/**
 * 〈一句话功能简述〉<br>
 * 〈使用链表创建栈和队列〉
 *
 * @author hanxinghua
 * @create 2021/9/6
 * @since 1.0.0
 */
public class StackQueueLinked<T> {


    public static void main(String[] args) {

        // myDeque();

        myStack();

    }

    /**
     *  栈，先进后出
     */
    private static void myStack() {
        StackQueueLinked<Integer> myStack = new StackQueueLinked<>();
        myStack.addFirst(1);
        myStack.addFirst(2);
        myStack.addFirst(3);
        myStack.printHeadWhile();
        System.out.println("-------");
        System.out.println(myStack.removeFirst());
        System.out.println(myStack.removeFirst());
        System.out.println(myStack.removeFirst());
    }

    /**
     * 双端队列
     */
    private static void myDeque() {
        StackQueueLinked<Integer> myDeque = new StackQueueLinked<>();
        myDeque.addFirst(1);
        myDeque.addFirst(2);
        myDeque.addFirst(3);
        myDeque.addLast(4);
        myDeque.addLast(5);
        myDeque.addLast(6);
        // 预期结果 321 456
        myDeque.printHeadWhile();
        System.out.println("-------");
        System.out.println(myDeque.removeFirst());
        // 预期结果 21 456
        myDeque.printHeadWhile();
        System.out.println("-------");
        System.out.println(myDeque.removeLast());
        // 预期结果 21 45
        myDeque.printHeadWhile();
        // 预期结果 54 12
        myDeque.printTailWhile();
        myDeque.clear();
        System.out.println("-------");
        System.out.println(myDeque.isEmpty());
    }


    public Node<T> head;
    public Node<T> tail;


    /**
     * 头添加
     *
     * @param data
     */
    public void addFirst(T data) {
        Node cur = new Node(data);
        if (head == null) {
            head = cur;
            tail = cur;
        } else {
            head.pre = cur;
            cur.next = head;
            head = cur;
        }
    }

    /**
     * 尾添加
     *
     * @param data
     */
    public void addLast(T data) {
        Node cur = new Node(data);
        if (tail == null) {
            head = cur;
            tail = cur;
        } else {
            tail.next = cur;
            cur.pre = tail;
            tail = cur;
        }

    }

    /**
     * 头删除
     */
    public T removeFirst() {
        if (head == null) {
            return null;
        }
        Node<T> cur = head;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = cur.next;
            head.pre = null;
            cur.next = null;
        }
        return cur.date;
    }

    /**
     * 尾删除
     */
    public T removeLast() {

        if (tail == null) {
            return null;
        }
        Node<T> cur = tail;
        if (tail == head) {
            head = null;
            tail = null;
        } else {
            tail = tail.pre;
            tail.next = null;
            cur.pre = null;
        }
        return cur.date;
    }


    /**
     * 头循环
     */
    public void printHeadWhile() {
        System.out.println("-------");
        // 必须赋值给新变量cur，不然head值该没有了。
        Node cur = head;
        while (cur != null) {
            System.out.println(cur.date);
            cur = cur.next;
        }
    }

    /**
     * 尾循环
     */
    public void printTailWhile() {
        System.out.println("-------");
        // 必须赋值给新变量cur，不然head值该没有了。
        Node cur = tail;
        while (cur != null) {
            System.out.println(cur.date);
            cur = cur.pre;
        }
    }


    /**
     * 清除
     */
    public void clear() {
        head = null;
        tail = null;
    }

    /**
     * 为空
     *
     * @return
     */
    public boolean isEmpty() {
        return head == null;
    }

    /**
     * 内部节点
     *
     * @param <T>
     */
    private static class Node<T> {
        public Node pre;
        public Node next;
        public T date;

        public Node(T date) {
            this.date = date;
        }

        public Node(T date, Node pre, Node next) {
            this.date = date;
            this.pre = pre;
            this.next = next;
        }
    }

}
